package SortStudy;

/**
 * 此类包含的排序方法有：
 * 冒泡排序
 * 插入排序
 * 希尔排序
 * 快速排序
 * 归并排序
 * 计数排序
 * 堆排序
 */
public class SortCore{

    /**
     * 泛型排序方法：采用冒泡排序 由小到大排序
     * 此排序方法会影响传入数组，用前请知晓
     * @param array 需要排序的数组
     * @param <T> 泛型类型
     * @return 返回处理后的结果
     */
    public static <T extends Comparable> T[] maoPaoSort(T[] array){
        if (array == null || array.length == 0) {
            return null;
        }
        for (int i = 0; i < array.length; i++) {
            for(int j=0;j<array.length;j++){
                if(array[i].compareTo(array[j])<0){
                    T temp=array[i];
                    array[i]=array[j];
                    array[j]=temp;
                }
            }
        }
        return array;
    }

    /**
     * 插入排序核心实现
     * @param a 排序数组
     */
    public static <T extends Comparable> T[] InsertionSort(T[] a){
        for(int i=1;i<a.length;i++){
            T key=a[i];
            int j=i-1;
            while(j>=0&&a[j].compareTo(key)>0){
                a[j+1]=a[j];
                j--;
            }
            a[j+1]=key;
        }
        return a;
    }

    /**
     * 希尔排序核心实现
     * @param a 排序数组
     * @param n 初始间距
     */
    public static <T extends Comparable> T[] ShellSort(T[] a,int n){
        int i,j,increment;
        T tem;
        for(increment=n/2;increment>0;increment/=2){
            for(i=increment;i<n;i++){
                tem=a[i];
                for(j=i;j>=increment;j-=increment){
                    if(tem.compareTo(a[j-increment])<0)
                        a[j]=a[j-increment];
                    else break;
                }
                a[j]=tem;
            }
        }
        return a;
    }



    //*****************************************************快速排序实现*********************************************************
    /**
    快速排序主函数
    参数： a：输入数组  Left：排序开始位置  Right：排序结束位置
    */
    public static <T extends Comparable> T[] quickSort(T[] a,int Left,int Right){
        int i,j;
        T Pivot;
        if(Left+3<=Right) {
            Pivot=Median3(a,Left,Right);
            i=Left;
            j=Right-1;
            for(;;){
                while(a[i].compareTo(Pivot)<0){i++;}
                while(a[j].compareTo(Pivot)>0){j--;}
                if(i<j){
                    Swap(a,i,j);
                }
                else
                    break;
            }
            Swap(a,i,Right);

            quickSort(a,Left,i-1);//对左边部分进行递归

            quickSort(a,i+1,Right);//对右边部分递归
        }else if(Left+2==Right){
            //当只有三个元素时进行简单排序
            easySort(a,Left,Right);
        }
        else if(Left+1==Right){
            //当只有两个元素时进行简单排序
            easySort(a,Left,Right);
        }
        return a;
    }

    /*
    key值寻找方法：中值法
      参数：a:输入数组  Left：数组第一个位置  Right：最后一个位置
      次方法的基本思想是在数组的第一个，最中间一个，最后一个元素中
      选择中间值作为key值，且和最后一个元素互换
    */
    public static <T extends Comparable> T Median3(T[] a, int Left, int Right) {
        int Center = (Left + Right) / 2;
        if (a[Left].compareTo(a[Center])>0 && a[Left].compareTo(a[Right])<0 || a[Left].compareTo(a[Center])<0 && a[Left].compareTo(a[Right])>0) {
            Swap(a, Left, Right);
        } else if (a[Center].compareTo(a[Right])>0 && a[Center].compareTo(a[Left])<0 || a[Center].compareTo(a[Right])<0 && a[Center].compareTo(a[Left])>0){
            Swap(a, Center, Right);
        } else if (a[Right].compareTo(a[Left])>0 && a[Right].compareTo(a[Center])<0 || a[Right].compareTo(a[Left])<0 && a[Right].compareTo(a[Center])>0) {
            Swap(a, Right, Right);
        }
        return a[Right];
    }

    /*
     * 交换函数
     * 它交换数组a中j和i位置的元素
     * */
    public static <T extends Comparable> void Swap(T[] a,int j,int i){
        T m;
        m=a[i];
        a[i]=a[j];
        a[j]=m;
    }

    /*
     * 简单排序，它主要解决当要排序的元素数目是3或2个的排序
     * */
    public static <T extends Comparable> void easySort(T[] a,int Left,int Right){
        int Center=Left+1;

        if(a[Left].compareTo(a[Center])>0) {
            Swap(a,Left,Center);
        }
        if(a[Left].compareTo(a[Right])>0){
            Swap(a,Left,Right);
        }
        if(a[Center].compareTo(a[Right])>0){
            Swap(a,Center,Right);
        }
    }
   //******************************************快速排序实现结束*******************************************************************

    //******************************************归并排序*****************************************************************
   //合并方法
    public static <T extends Comparable> void merge(T[] a,int left,int mid,int right){
       T[] tmp= (T[]) new Object[a.length];//辅助数组
       int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针

       while(p1<=mid && p2<=right){
           if(a[p1].compareTo(a[p2])<=0)
               tmp[k++]=a[p1++];
           else
               tmp[k++]=a[p2++];
       }

       while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
       while(p2<=right) tmp[k++]=a[p2++];//同上

       //复制回原素组
       for (int i = left; i <=right; i++)
           a[i]=tmp[i];
   }

    //排序主方法
    public static <T extends Comparable> T[] mergeSort(T[] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
        return a;
    }
   //******************************************归并排序实现结束******************************************************************


    /**
     * 计数排序
     * @param a 排序数组
     * @param b 输出数组
     * @param k 范围最大值
     */
    public void CountingSort(int[] a,int[] b,int k) {
        int[] c=new int [k];
        int j,i;

        for(i=0;i<k;i++)//这里java代码里可以不要，因为默认0
            c[i]=0;

        for(j=0;j<a.length;j++)
            c[a[j]] = c[a[j]] + 1;

        for (i=1; i < k; i++)
            c[i] = c[i] + c[i-1];

        for (j = a.length - 1; j >= 0; j--) {
            b[c[a[j]]-1] = a[j];//注意这里的b数组里面一定要-1
            c[a[j]] = c[a[j]] - 1;
        }
    }

    //*************************************************堆排序*****************************************************
    static class Heap<T extends Comparable> {
        public T[] array;//存储元素的数组
        public int count;//描述堆中存在元素的个数
        public int capacity;//堆的大小
        public int heap_type;//最大堆或最小堆
        //创建堆构造方法
        public Heap(int capacity,int heap_type) {
            this.capacity=capacity;
            this.heap_type=heap_type;
            this.count=0;
            this.array= (T[]) new Object[capacity];
        }
        //得到父母节点的位置
        public int Parent(int i)
        {
            if(i<=0||i>this.count)
                return -1;
            return (i-1)/2;
        }
        //得到左孩子节点的位置
        public int LeftChild(int i)
        {
            int left=2*i+1;
            if(left>=this.count)
                return -1;
            return left;
        }
        //得到右孩子节点的位置
        public int RightChild(int i)
        {
            int right=2*i+2;
            if(right>=this.count)
                return -1;
            return right;
        }
        //堆化元素
        public void PercolateDown(int i)
        {
            int l,r,max;
            T temp;
            l=LeftChild(i);
            r=RightChild(i);
            if(l==-1&&r==-1)
                return;
            if(l!=-1&&this.array[l].compareTo(this.array[i])>0)
                max=l;
            else
                max=i;
            if(r!=-1&&this.array[r].compareTo(this.array[max])>0)
                max=r;

            if(max==i)
                return;
            else
            {
                temp=this.array[i];
                this.array[i]=this.array[max];
                this.array[max]=temp;
            }
            PercolateDown(max);
        }

        //扩展堆
        void ResizeHeap()
        {
            T []array_old= (T[]) new Object[this.capacity];
            System.arraycopy(this.array,0,array_old,0,this.count-1);//复制方法
            this.array= (T[]) new Object[this.capacity*2];
            if(this.array==null){
                System.out.println("Memory Error");
                return;
            }
            for(int i=0;i<this.capacity;i++)
            {
                this.array[i]=array_old[i];

            }
            this.capacity *=2;
            array_old=null;

        }
        //数组建堆
        void BuildHeap(Heap h, T[] A, int n) {
            if(h==null) h=new Heap(A.length,1);
            while(n>this.capacity)
                h.ResizeHeap();

            for(int i=0;i<n;i++)//数组赋值
            {
                h.array[i]=A[i];

            }
            this.count=n;

            for(int i=(n-1)/2;i>=0;i--)//节点堆化
                h.PercolateDown(i);
        }

        //堆排序
        T[] Heapsort(Heap h, T[] A, int n) {
            int i;
            T temp;
            BuildHeap(h,A,n);
            h.count=n;

            for(i=n-1;i>=0;i--)
            {
                temp= (T) h.array[0];
                A[i]=temp;
                h.array[0]=h.array[h.count-1];
                h.count--;
                h.PercolateDown(0);

            }
            return A;
        }
    }

}
